function MapGenerator() {
  
  this.NUM_LEVELS = 4; // Number of different generatable levels.
 
  
  this.staringPositions = [
    { spawn : { x : 12, y : 12 }, yggdrasil : { x : 51, y : 51 } },
    { spawn : { x : 51, y : 12 }, yggdrasil : { x : 12, y : 51 } },
    { spawn : { x : 12, y : 51 }, yggdrasil : { x : 51, y : 12 } },
    { spawn : { x : 51, y : 51 }, yggdrasil : { x : 12, y : 12 } },
  ];

    
  this.treeDensity = [0.5, 0.55, 0.62, 0.72, 0.85];
  
  
  this.itemTileIDs = [  
    config.APPLE_TILE_ID,
    config.BANANA_TILE_ID,
    config.BREAD_TILE_ID,
    config.MEAT_TILE_ID,
    config.RICE_TILE_ID,
   
    config.ENVELOPE_PART_TILE_ID,
    config.ROPE_TILE_ID,
    config.BALLAST_SACK_TILE_ID,
    config.BURNER_TILE_ID,
    config.BASKET_TILE_ID,
    
    config.MACHETE_TILE_ID,
    config.AXE_TILE_ID,
    config.CHAINSAW_TILE_ID,
  ];
  
  // Defines the density of the single items per level
  
  
  this.itemDensity = [];
  
  this.init = function() {
    for (var i = 1; i <= this.NUM_LEVELS; i++) {
      this.itemDensity[i] = [ 
 
        config.levels[i].numApples,
        config.levels[i].numBananas,
        config.levels[i].numBread,
        config.levels[i].numMeat,
        config.levels[i].numRice,
        
        config.REQUIRED_ENVELOPE_PARTS*config.levels[i].pieceDistribution,
        config.REQUIRED_ROPES*config.levels[i].pieceDistribution, 
        config.REQUIRED_BALLAST_SACKS*config.levels[i].pieceDistribution, 
        config.REQUIRED_BURNERS*config.levels[i].pieceDistribution, 
        config.REQUIRED_BASKETS*config.levels[i].pieceDistribution,
        
        config.levels[i].numMachetes, 
        config.levels[i].numAxes, 
        config.levels[i].numChainsaws 
        ];
    }[i]
  }
  
  
  this.generateMap = function(level) {

    level =  setInRange(level, 0, this.NUM_LEVELS);
    
    var tileMap = [];
    
    // Basic map
    this.generateGrass(level, tileMap);   
    
    this.generateCliffBorder(level, tileMap);
      
    this.generateRiver(level, tileMap);

    var tmp = this.generateStartEnd(level, tileMap);
    var spawnPoint = tmp.startPoint;
    var endPoint = tmp.endPoint;
    
    this.generateDarkForests(level, tileMap, spawnPoint, endPoint);       
    this.generateCliffClumbs(level, tileMap, spawnPoint, endPoint);
    this.generateItems(level, tileMap, spawnPoint, endPoint);
    this.generateStones(level, tileMap, spawnPoint, endPoint);
    this.generateVegetation(level, tileMap, spawnPoint, endPoint);
    
    return tileMap;
  };
  
  
  /**
  * Genereates the grass background of the map.
  * Also adds some rocks in the corners.
  * @parm map map where the grass is produced to
  */
  this.generateGrass = function(level, tileMap) {
    
    var mapMidpoint = (map.SIZE - 1) / 2;
    
    for(var x = 0; x < map.SIZE; x++) {
      tileMap[x] = [];
      for(var y = 0; y < map.SIZE; y++) {
        
        tileMap[x][y] = rand(config.GRASS_MIN_ID, config.GRASS_MAX_ID);
              
        if(distance(mapMidpoint, mapMidpoint, x, y) > 40.5) {
          tileMap[x][y] = this.generateRandomRock();
        }
      }
    }   
  };
  
  
  /**
  * Generate the cliff border around the map.
  */
  this.generateCliffBorder = function(level, tileMap) {
    
    for(var x = 0; x < map.SIZE; x++) {
      tileMap[x][0] = this.generateRandomRock();
      if(rand(0, 1) == 1) {
        tileMap[x][1] = this.generateRandomRock();
        if(rand(0, 2) == 1) {
          tileMap[x][1] = this.generateRandomRock();
        }
      }
      tileMap[x][map.SIZE - 1] = this.generateRandomRock();
      if(rand(0, 1) == 1) {
        tileMap[x][map.SIZE - 2] = this.generateRandomRock();
        if(rand(0, 2) == 1) {
          tileMap[x][map.SIZE - 3] = this.generateRandomRock();
        }
      }
    }
    
    for(var y = 0; y < map.SIZE; y++) {
      tileMap[0][y] = this.generateRandomRock();
      if(rand(0, 1) == 1) {
        tileMap[1][y] = this.generateRandomRock();
        if(rand(0, 2) == 1) {
          tileMap[1][y] = this.generateRandomRock();
        }
      }
      tileMap[map.SIZE - 1][y] = this.generateRandomRock();
      if(rand(0, 1) == 1) {
        tileMap[map.SIZE - 2][y] = this.generateRandomRock();
        if(rand(0, 2) == 1) {
          tileMap[map.SIZE - 3][y] = this.generateRandomRock();
        }
      }
    }
  };
  
  
  /**
  * Generate the river
  */
  this.generateRiver = function(level, tileMap) {
    var riverDir = 0;
    var twistCounter = 2;
    var riverAxis = rand(0, 1);
    var riverX = rand(11, map.SIZE - 12);
    var riverY = 0;
    
    if(riverAxis == 0) {
      tileMap[riverY][riverX] = this.generateRandomVerticalRiver();
    } else {
      tileMap[riverX][riverY] = this.generateRandomHorizontalRiver();
    }
    
    while(riverY < map.SIZE - 2) {
      
      if(twistCounter > 0) {
        twistCounter--;
      }
      
      if(riverDir == 0) {
        riverY++;
        if(twistCounter == 0) {
          var possibleNewDirs = [-1, 0, 0, 0, 0, 0, 1];
          riverDir = possibleNewDirs[rand(0, 6)];
        }
        if(riverX <= 8 && riverDir == -1) {
          riverDir = 1;
        }
        if(riverX > map.SIZE - 8 && riverDir == 1) {
          riverDir = -1;
        }
        if(riverY == map.SIZE - 2) {
          riverDir = 0;
        }
        
        if(riverDir == 0) {
          if(riverAxis == 0) {
            tileMap[riverY][riverX] = this.generateRandomVerticalRiver();
          } else {
            tileMap[riverX][riverY] = this.generateRandomHorizontalRiver();
          }
          
        } else if(riverDir == -1) {
          if(riverAxis == 0) {
            tileMap[riverY][riverX] = 60;
          } else {
            tileMap[riverX][riverY] = 60;
          }
          twistCounter = 3;
          
        } else if(riverDir == 1) {
          if(riverAxis == 0) {
            tileMap[riverY][riverX] = 61;
          } else {
            tileMap[riverX][riverY] = 63;
          }
          twistCounter = 3;
        }
        
        
      } else if(riverDir == -1) {
        riverX--;
        if(twistCounter == 0) {
          var possibleNewDirs = [-1, -1, 0];
          riverDir = possibleNewDirs[rand(0, 2)];
        }
        if(riverX <= 8) {
          riverDir = 0;
        }
        if(riverY == map.SIZE - 2) {
          riverDir = 0;
        }
        
        if(riverDir == 0) {
          if(riverAxis == 0) {
            tileMap[riverY][riverX] = 62;
          } else {
            tileMap[riverX][riverY] = 62;
          }
          twistCounter = 3;
          
        } else if(riverDir == -1) {
          if(riverAxis == 0) {
            tileMap[riverY][riverX] = this.generateRandomHorizontalRiver();
          } else {
            tileMap[riverX][riverY] = this.generateRandomVerticalRiver();
          }
        }
        
        
      } else if(riverDir == 1) {
        riverX++;
        if(twistCounter == 0) {
          var possibleNewDirs = [0, 1, 1];
          riverDir = possibleNewDirs[rand(0, 2)];
        }
        if(riverX > map.SIZE - 8) {
          riverDir = 0;
        }
        if(riverY == map.SIZE - 2) {
          riverDir = 0;
        }
        
        if(riverDir == 0) {
          if(riverAxis == 0) {
            tileMap[riverY][riverX] = 63;
          } else {
            tileMap[riverX][riverY] = 61;
          }
          twistCounter = 3;
          
        } else if(riverDir == 1) {
          if(riverAxis == 0) {
            tileMap[riverY][riverX] = this.generateRandomHorizontalRiver();
          } else {
            tileMap[riverX][riverY] = this.generateRandomVerticalRiver();
          }
        }
        
      }
    }
    riverY++;
    if(riverAxis == 0) {
      tileMap[riverY][riverX] = this.generateRandomVerticalRiver();
    } else {
      tileMap[riverX][riverY] = this.generateRandomHorizontalRiver();
    }
    
  }
  
  
  /**
  * @return tile coordinates of spawn and end point
  */
  this.generateStartEnd = function(level, tileMap) {
    //TODO: Change names
    var hasSpawnAndYggdrasil = false;
    var spawnX = 0;
    var spawnY = 0;
    
    var yggdrasilX = 0;
    var yggdrasilY = 0;
    
    while(!hasSpawnAndYggdrasil) {
      var constellation = this.staringPositions[rand(0, 3)];
      spawnX = constellation.spawn.x + rand(-5, 5);
      spawnY = constellation.spawn.y + rand(-5, 5);
      yggdrasilX = constellation.yggdrasil.x + rand(-5, 5);
      yggdrasilY = constellation.yggdrasil.y + rand(-5, 5);
      hasSpawnAndYggdrasil = true;
      for(var x = spawnX - 2; x < spawnX + 2; x++) {
        for(var y = spawnY - 2; y < spawnY + 2; y++) {
          if(tileMap[x][y] > 7) {
            hasSpawnAndYggdrasil = false;
          }
        }
      }
      for(var x = yggdrasilX - 2; x < yggdrasilX + 2; x++) {
        for(var y = yggdrasilY - 2; y < yggdrasilY + 2; y++) {
          if(tileMap[x][y] > 7) {
            hasSpawnAndYggdrasil = false;
          }
        }
      }
    }
    tileMap[spawnX][spawnY] = config.SPAWN_TILE_ID;
    
    if (level == config.NUM_LEVELS) {
      tileMap[yggdrasilX][yggdrasilY] = config.BASKET_TILE_ID;
    }
    else {
        tileMap[yggdrasilX][yggdrasilY] = config.YIGGDRASIL_TILE_ID;
    }
    
    
    return { startPoint: {x: spawnX, y: spawnY}, 
              endPoint: {x: yggdrasilX, y: yggdrasilY}
            };
  };
  
  
  this.generateDarkForests = function(level, tileMap, spawnPoint, endPoint) {
    var i = 0;
    while(i < 4) {
      var clumpX = rand(5, map.SIZE - 6);
      var clumpY = rand(5, map.SIZE - 6);
      var locationGood = true;
      var size = 2.4;
      for(var x = clumpX - 5; x < clumpX + 5; x++) {
        for(var y = clumpY - 5; y < clumpY + 5; y++) {
          if(tileMap[x][y] > 7) {
            locationGood = false;
          }
        }
      }
      if(locationGood) {
        var possibleFrequencies = [5, 7, 9, 11];
        var frequency = possibleFrequencies[rand(0, 3)];
        var offset = randFloat(0.1, 2.5);
        for(var x = clumpX - 4; x < clumpX + 4; x++) {
          for(var y = clumpY - 4; y < clumpY + 4; y++) {
            var angle1 = offset + (Math.atan2(clumpX - x, clumpY - y) * frequency);
            var angle2 = (offset * 3) + (Math.atan2(clumpX - x, clumpY - y) * 3);
            var maxDist = size * (1 + (0.1 * Math.sin(angle1)) + (0.1 * Math.sin(angle2)));
            if(distance(clumpX, clumpY, x, y) < maxDist) {
              tileMap[x][y] = 40;
            }
          }
        }
        i++;
      }
    }
    
    // Filling of forests
    for(var x = 0; x < map.SIZE; x++) {
      for(var y = 0; y < map.SIZE; y++) {
        if(tileMap[x][y] == 40) {
          if(this.isDarkForest(tileMap[x - 1][y]) && this.isDarkForest(tileMap[x + 1][y]) && this.isDarkForest(tileMap[x][y - 1]) && this.isDarkForest(tileMap[x][y + 1]) &&
             this.isDarkForest(tileMap[x - 1][y - 1]) && this.isDarkForest(tileMap[x - 1][y + 1]) && this.isDarkForest(tileMap[x + 1][y - 1]) && this.isDarkForest(tileMap[x + 1][y + 1])) {
            tileMap[x][y] = 64;
          } else if(rand(0, 1) == 1) {
            tileMap[x][y] = 44;
          }
        }
      }
    }
    
  };
  
  
  this.generateCliffClumbs = function(level, tileMap, spawnPoint, endPoint) {
    var i = 0;
    while(i < 6) {
      var clumpX = rand(5, map.SIZE - 6);
      var clumpY = rand(5, map.SIZE - 6);
      var locationGood = true;
      var size = 2.0;
      for(var x = clumpX - 5; x < clumpX + 5; x++) {
        for(var y = clumpY - 5; y < clumpY + 5; y++) {
          if(tileMap[x][y] > 7) {
            locationGood = false;
          }
        }
      }
      if(locationGood) {
        var possibleFrequencies = [5, 7, 9, 11];
        var frequency = possibleFrequencies[rand(0, 3)];
        var offset = randFloat(0.1, 2.5);
        for(var x = clumpX - 4; x < clumpX + 4; x++) {
          for(var y = clumpY - 4; y < clumpY + 4; y++) {
            var angle1 = offset + (Math.atan2(clumpX - x, clumpY - y) * frequency);
            var angle2 = (offset * 3) + (Math.atan2(clumpX - x, clumpY - y) * 3);
            var maxDist = size * (1 + (0.1 * Math.sin(angle1)) + (0.1 * Math.sin(angle2)));
            if(distance(clumpX, clumpY, x, y) < maxDist) {
              tileMap[x][y] = this.generateRandomRock();
            }
          }
        }
        i++;
      }
    }
  };
  
  
  this.generateItems = function(level, tileMap, spawnPoint, endPoint) {
    
    if(level == 1) {
      var placed = false;
      while(!placed) {
        var randX = spawnPoint.x + rand(-1, 1);
        var randY = spawnPoint.y + rand(-1, 1);
        if(tileMap[randX][randY] >= 0 && tileMap[randX][randY] <= 7) {
          tileMap[randX][randY] = 13;
          placed = true;
        }
      }
    }
    
    for(var item = 0; item < 13; item++) {
      var density = this.itemDensity[level][item];
      var tileId = this.itemTileIDs[item];
      
      var numItems = density;
      
      if( item == config.ENVELOPE_PART_TILE_ID) {
        density -= hero.envelopeParts;
      }
      else if( item == config.ROPE_TILE_ID) {
        density -= hero.ropes;
      }
      else if( item == config.BALLAST_SACK_TILE_ID) {
        density -= hero.ballastSacks;
      }
      else if( item == config.BURNER_TILE_ID) {
        if (level == this.NUM_LEVELS - 1) {
          density = 1;
        }
        else {
          density = 0;
        }
      }
      else if( item == config.BASKET_TILE_ID) { // TODO: Remove BASKET_TILE_ID from item list and remove this.
          density = 0;     
      }
      
      for(var i = 0; i < density; i++) {
        var placed = false;
        while(!placed) {
          var randX = rand(1, map.SIZE - 1);
          var randY = rand(1, map.SIZE - 1);
          if(tileMap[randX][randY] >= 0 && tileMap[randX][randY] <= 7 && this.isNotReserved(randX, randY, spawnPoint.x, spawnPoint.y, endPoint.x, endPoint.y)) {
            tileMap[randX][randY] = tileId;
            placed = true;
          }
        }
      }
    }
  };
  
  
  /**
  * Generates stones and single cliffs
  */
  this.generateStones = function(level, tileMap, spawnPoint, endPoint) {
    for(var i = 0; i < 120; i++) {
      var randX = rand(1, map.SIZE - 1);
      var randY = rand(1, map.SIZE - 1);
      if(tileMap[randX][randY] >= 0 && tileMap[randX][randY] <= 7 && this.isNotReserved(randX, randY, spawnPoint.x, spawnPoint.y, endPoint.x, endPoint.y)) {
        tileMap[randX][randY] = this.generateRandomStone()
      }
    }
     
    // Single Cliffs
    for(var i = 0; i < 12; i++) {
      var randX = rand(1, map.SIZE - 1);
      var randY = rand(1, map.SIZE - 1);
      if(tileMap[randX][randY] >= 0 && tileMap[randX][randY] <= 7 && this.isNotReserved(randX, randY, spawnPoint.x, spawnPoint.y, endPoint.x, endPoint.y)) {
        tileMap[randX][randY] = this.generateRandomRock();
      }
    }
  };
  
  
  this.generateVegetation = function(level, tileMap, spawnPoint, endPoint) {
    for(var x = 0; x < map.SIZE; x++) {
      for(var y = 0; y < map.SIZE; y++) {
        if(tileMap[x][y] >= 0 && tileMap[x][y] <= 7 && this.isNotReserved(x, y, spawnPoint.x, spawnPoint.y, endPoint.x, endPoint.y)) {
          if(zeroOrOne(this.treeDensity[level]) == 1) {
            tileMap[x][y] = rand(24, 39);
          }
        }
      }
    }
  };
  

  this.generateRandomRock = function() {
    return config.ROCK_MIN_ID, config.ROCK_MAX_ID;
  }


  this.generateRandomStone = function() {
    return rand(config.STONE_MIN_ID, config.STONE_MAX_ID);
  }

  
  this.generateRandomHorizontalRiver = function() {
    return rand(config.RIVER_HOR_MIN_ID, config.RIVER_HOR_MAX_ID)
  }
  
  
  this.generateRandomVerticalRiver = function() {
    return rand(config.RIVER_VER_MIN_ID, config.RIVER_VER_MAX_ID)
  }


  this.isNotReserved = function(x, y, spawnX, spawnY, yggdrasilX, yggdrasilY) {
    return distance(x, y, spawnX, spawnY) > 3 && distance(x, y, yggdrasilX, yggdrasilY) > 2;
  };
  
  
  this.isDarkForest = function(tile) {
    return tile == 40 || tile == 44 || tile == 64 || tile == 65;
  };
  
}